Inferring depth from images or videos has been an important problem in computer vision research. Among a numerous approaches that have been proposed, triangulation based depth measurement is popular and well-understood. However, conventional stereo depth reconstruction algorithms based on triangulation have difficulty in finding correct correspondence in a pair of images when the scene is untextured or has repetitive patterns.
To help finding the correct correspondences between a pair of images, one can artificially create texture, for example, using additional varying illumination (often implemented as a light projector) as used in space-time stereo methods. Temporal illumination changes create a signature in an intensity profile at each pixel, and by matching the spatio-temporal block of neighboring pixels, some of the ambiguous correspondence between pixels of a pair of images can be resolved. However, space-time stereo methods still need to scan over epipolar lines to find correct correspondences at the expanse of increased computational overhead.
To reduce computational overhead in space-time stereo implementation, structured light methods replace one of the cameras used in space-time stereo implementation with a projector. By projecting certain light patterns, one can infer which ray from the projector reached the scene point corresponding to the pixels in the captured image, and depth can be reconstructed by means of triangulation. Specifically, in a camera-projector system for depth reconstruction, a coding method, such as Gray codes and Direct coding, encodes projected ray locations into projection patterns, where a projected ray needs to be uniquely identifiable
There are three major challenges that conventional projection patterns for a structured light method may fail to work, especially in an indoor environment under natural illumination. The first challenge concerns a range aspect of depth reconstruction. A desired depth range in an indoor environment under natural illumination is much larger than traditional approaches (at least from 0.5 m to 5 m). As the distance to the surface in the scene to be reconstructed increases, the brightness of returned projection patterns is attenuated by the square of the distance.
The second challenge is related to illumination. To detect projection patterns under natural indoor illumination, the dynamic range and signal-to-noise ratio (SNR) of a camera used in a reconstruction system or the strength of projected light must be increased. In reality, there are certain practical and safety limitations in both approaches. For example, projected light must be safe to human eyes, which puts limits on the strength of the projected light to be used.
The last challenge concerns the scene to be reconstructed. Objects in a scene to be reconstructed may have various colors, textures and shapes, which make the strength of reflected light from projection vary greatly. These variations and challenges described above, e.g., depth range and illumination, make it difficult to encode projected ray locations into projection patterns using conventional coding algorithms. For example, Gray codes algorithm requires capturing many projection patterns, and it is not appropriate for dynamic scene reconstruction. Direct coding is insufficient when the intensity range of a captured pattern is small (due to distance or surface color) because Direct coding requires accurate measure of intensity variations.
Typical projection patterns for structured light methods are stripe-patterns and multi-slit patterns. Stripe patterns generally consist of parallel adjacent bands, and multi-slit patterns consist of narrow bands separated by black gaps. The objective of any coding strategy (that encodes the locations of projected rays into projection patterns) is that, given an element of the projection pattern, e.g., a stripe or a slit, its position in the pattern can be obtained by inspecting a local neighborhood of elements around it. Classical De Bruijn sequences are often used by a coding method to encode and decode locations of projected rays because a De Bruijn sequence can be used to represent the locations of projected rays.
Given a set of alphabets, A={a1, . . . , ak} and a positive integer n, a classical De Bruijn sequence B(n, A) is a cyclic sequence of the alphabets in which all possible length-n sequences of alphabets A appear exactly once (known as window property). FIG. 1A illustrates some examples of classical De Bruijn sequences. For example, given a set of alphabets, A={0, 1} and n=2, B(2, {0, 1}) is a De Bruijn sequence containing all length of 2 sequences of {0, 1}, i.e., 00, 01, 11, 10. The length of a De Bruijn sequence is kn. Given a set of alphabets, A={a1, . . . , ak} and a positive integer n, there exist many distinct De Bruijn sequences. For example, sequence 0011 is one of these De Bruijn sequences.
To generate classical De Bruijn sequences, a De Bruijn graph is normally used. To simplify description of an embodiment of the invention, a De Bruijn graph used to generate classical De Bruijn sequences is referred to as classical De Bruijn graph herein. By definition in graph theory, a De Bruijn graph GB(n, A) is a directed graph {V, E}, where V is a set of all possible lengthen permutations of A, {a1 a1 . . . a1, a1 a1 . . . a2, . . . , ak ak . . . ak}, and E is the set of directed edges {(s1 s1 . . . sn-1, s1 s2 . . . Sn-1 sm)}. A De Bruijn graph is Eulerian and Hamiltonian. The Euler cycles and Hamiltonian cycles of a De Bruijn graph are De Bruijn sequences. A Hamiltonian cycle of GB(n, A) or an Euler cycle of GB(n−1, A) generates a De Bruijn sequence B(n, A).
FIG. 1B is a classical De Bruijn graph whose Hamiltonian cycles and Eulerian cycles generate classical De Bruijn sequences illustrated in FIG. 1A. Similarly, FIG. 1C is another classical De Bruijn graph whose Hamiltonian cycles generate classical De Bruijn sequences illustrated in FIG. 1A. For example, the first example sequence in FIG. 1A, B(2, {0, 1})=0011 is generated from a Hamiltonian cycle of FIG. 1B, and the second sequence, B(3, {0, 1})=00010111 is generated from an Eulerian cycle of the same graph (FIG. 1B). The third sequence, B(2, {0, 1, 2})=001122021 is generated from a Hamiltonian cycle of FIG. 1C.
A De Bruijn sequence has many consecutive identical or recurring alphabets, such as 00 or 111 in B(2, {0, 1})=0011 and B(3, {0, 1})=00010111. To encode projected ray locations into projection patterns using classical De Bruijn sequences, a conventional coding method, such as Direct coding, is impossible to distinguish such recurring alphabets in a captured image by a camera. For example, Direct coding uses shifted versions of a continuous periodic intensity pattern (e.g., a sine function) and measures the phase of the intensity pattern at each pixel from images being observed. As such, Direct coding requires accurate measurement of intensity variations. However, consecutive identical or recurring alphabets in classical De Bruijn sequences make Direct coding fail to work, especially in an indoor environment. To get around this problem, one may define alphabets as special patches, or place separators between alphabets in a classical De Bruijn sequence. However, both approaches (e.g., special patches and separators) result in sparse depth map reconstruction, and extra alphabets are often needed for the separators. For example, conventional XOR coding method uses alphabets as operands of XOR on each color channel, and detecting color changes in a captured image. This method may generate dense depth maps with multi-pass dynamic programming and shifted projection patterns over multiple frames. However the length-n subsequences in the resulting projection pattern from coding the alphabets are not unique anymore, thus, XOR coding method cannot be used for space-time stereo reconstruction methods. Also to detect one length-n subsequence, XOR coding method needs to observe n color changes, which needs n+1 stripes to be seen. Consequently, the efficiency of fast, reliable and dense depth reconstruction of images or videos is degraded. Optimized projection patterns for depth reconstruction are needed.